home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / man / b_stack.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  1.4 KB  |  49 lines
  1.  
  2. {\magonebf 3.5 Bounded Stacks (b\_stack) }
  3.  
  4. \decl b\_stack E
  5.  
  6. {\bf 1. Definition}
  7.  
  8. An instance $S$ of the parmaterized data type \name\ is a stack 
  9. (see section 2.3) of bounded size. 
  10.  
  11. \bigskip
  12. {\bf 2. Creation}
  13.  
  14. \create S (n)   
  15.  
  16. creates an instance \var\ of type \name\ that can hold up to $n$ elements.
  17. \var\ is initialized with the empty stack.
  18.  
  19.  
  20. {\bf 3. Operations}
  21. \+\cleartabs & \hskip 2truecm & \hskip 4truecm &\cr
  22. \+\op E       top   {}        
  23.                               {returns the top element of \var}
  24. \+\nop                        {\precond $S$ is not empty.}
  25. \smallskip
  26. \+\op E       pop   {}        
  27.                               {deletes and returns the top element of \var}
  28. \+\nop                        {\precond $S$ is not empty.}
  29. \smallskip
  30. \+\op void    push  {E\ x}    
  31.                               {adds $x$ as new top element to \var}
  32. \+\nop                        {\precond $S$.size() $< n$.}
  33. \smallskip
  34. \+\op void    clear {}        
  35.                               {makes \var\ the empty stack.}
  36. \smallskip
  37. \+\op int     size  {}        
  38.                               {returns the size of \var.}
  39. \smallskip
  40. \+\op bool    empty {}        
  41.                               {returns true if \var\ is empty, false otherwise.}
  42.  
  43. \bigskip
  44. {\bf 4. Implementation}
  45.  
  46. Bounded Stacks are implemented by \CC vectors. All operations take 
  47. time $O(1)$. The space requirement is $O(n)$.
  48.  
  49.